package main

import (
	"container/heap"
	"fmt"
	"time"
)

type Item struct {
	key      int
	value    string
	priority int64 //用时间戳表示priority
	index    int
	expired  int //过期时间
}

type PriorityQueue []*Item

/*先实现一个小根堆*/
func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

/**/

func (pq *PriorityQueue) update(item *Item, key int, value string, priority int64) {
	item.key = key
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

type LRUCache2 struct {
	capacity int
	pq       PriorityQueue
	m        map[int]*Item
}

func NewCacher2(cap int) *LRUCache2 {
	return &LRUCache2{
		capacity: cap,
		pq:       make(PriorityQueue, 0, cap),
		m:        make(map[int]*Item, cap),
	}
}

func (lc *LRUCache2) Get(key int) string {
	if item, exist := lc.m[key]; !exist {
		return "not exist"
	} else {
		ts := time.Now().UnixMilli()
		expired := time.Duration(item.expired) * time.Second
		if item.priority+expired.Milliseconds() < ts { //检查是否到期
			delete(lc.m, key)               //已到期，删除map中对应的元素
			heap.Remove(&lc.pq, item.index) //删除heap中对应的元素
			return "expired"
		} else {
			return item.value
		}
	}
}

func (lc *LRUCache2) Set(key int, value string, expired int) string {
	if item, exist := lc.m[key]; exist {
		ts := time.Now().UnixMilli()
		lc.pq.update(item, key, value, ts)
		item.expired = expired
		return lc.m[key].value
	} else {
		if len(lc.m) == lc.capacity {
			oldItem := heap.Pop(&lc.pq) //超出容量直接删除最早的元素
			delete(lc.m, oldItem.(*Item).key)
		}
		newItem := &Item{
			key:      key,
			value:    value,
			priority: time.Now().UnixMilli(),
			expired:  expired,
		}
		heap.Push(&lc.pq, newItem) //插入新的元素
		lc.m[key] = newItem
		return lc.m[key].value
	}
}

func main() {
	lc := NewCacher2(4)
	fmt.Println(lc.Get(1)) //not exist
	fmt.Println(lc.Set(1, "hello world", 10)) //hello world
	time.Sleep(time.Millisecond * 2)
	// m := 15
	// for m > 0 { //测试到期后的输出
	// 	fmt.Println(lc.Get(1))
	// 	time.Sleep(1 * time.Second)
	// 	m--
	// }
	fmt.Println(lc.Set(2, "hello world22", 10)) //hello world22
	time.Sleep(time.Millisecond * 2)
	fmt.Println(lc.Set(3, "hello world333", 10)) //hello world333
	time.Sleep(time.Millisecond * 2)
	fmt.Println(lc.Set(4, "hello world4444", 10)) //hello world4444
	time.Sleep(time.Millisecond * 2)
	fmt.Println(lc.Set(5, "hello world55555", 10)) //hello world55555
	fmt.Println("------------------------------------------------")
	fmt.Println(lc.Get(1)) //not exist
	fmt.Println(lc.Get(2)) //hello world22
	fmt.Println(lc.Get(3)) //hello world333
	fmt.Println(lc.Get(4)) //hello world4444
	fmt.Println(lc.Get(5)) //hello world55555
}
